﻿//TOP - K问题：即求数据结合中前K个最⼤的元素或者最⼩的元素，⼀般情况下数据量都⽐较⼤。//⽐如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
void CreateData()
{
	//造数据
	int n = 100000;
	srand((unsigned int)time(NULL));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("CreateData()::open()");
		exit(1);
	}
	//写数据
	for (int i = 0; i < n; ++i)
	{
		int x = (rand()+i) % 100000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//向下调整法
void AdjustDown(int* arr,int parent,int n)
{
	int child = 2 * parent + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void topk()
{
	//找前10强数据
	int k = 0;
	printf("请输入K");
	scanf("%d", &k);
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("topk()::fopen()");
		exit(1);
	}
	int val = 0;
	//申请k个大小的空间
	int* minHeap = (int*)malloc(sizeof(int) * k);
	if (minHeap == NULL)
	{
		perror("topk()::malloc()");
		exit(1);
	}
	
	for (int i = 0; i < k; ++i)
	{
		fscanf(fout, "%d", &minHeap[i]);
	}
	//建立小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(minHeap, i, k);
	}
	//遍历剩下的n-k个数，跟堆顶比较，谁大谁入堆
	int data = 0;
	//读数据
	while (fscanf(fout, "%d", &data) != EOF)
	{
		if (data > minHeap[0])
		{
			minHeap[0] = data;
			AdjustDown(minHeap, 0, k); //调整
		}
	}
	for (int i = 0; i < k; ++i)
	{
		printf("%d ", minHeap[i]);
	}
	printf("\n");
	fclose(fout);
}

int main()
{
	//CreateData();
	topk();
	return 0;
}